一、學習目標

• 會用 Binary Lifting（倍增法）在 O(logN) 內處理 k-th 祖先、LCA、兩點距離。
• 知道前處理要素：depth[]、up[v][j]（v 的 2^j階祖先）、可選 tin/tout 判祖孫。

二、觀念說明

• 前處理一個根（CSES 通常為 1）。DFS 做：
  • depth[v] = depth[p] + 1
  • up[v][0] = p，up[v][j] = up[up[v][j-1]][j-1]（若存在）
• k-th 祖先：把 k 的二進位位元逐一抬升 v。
• LCA(u,v)：先把較深者 u 抬到與 v 同深；若 u!=v 就從大到小嘗試把 u,v 同步往上跳，直到它們父親相同；回傳 up[u][0]。
• 距離：dist(u,v) = depth[u] + depth[v] - 2 * depth[lca(u,v)]。
• 安全邊界：若往上跳到 0 代表不存在（CSES 用 0 當「無祖先」）。

三、CSES觀念說明

題目1:Company Queries I

原題:
https://cses.fi/problemset/task/1687

題意:
給定一棵以 1 為根的樹（每點給父親），處理 q 次查詢：問節點 x 的 第 k 個祖先（不存在輸出 -1）。

解題思路:

• 建 up[x][j] 與 depth[]。
• 查詢時用 倍增 將 x 依 k 的位元往上跳，若中途為 0 則 -1。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, q;
    cin >> n >> q;
    const int LOG = 20;
    vector<vector<int>> up(LOG, vector<int>(n+1, 0));
    for(int v=2; v<=n; ++v){
        int p; cin >> p;
        up[0][v] = p; // 父親
    }
    // up[j][1..n]
    for(int j=1; j<LOG; ++j){
        for(int v=1; v<=n; ++v){
            int mid = up[j-1][v];
            up[j][v] = (mid ? up[j-1][mid] : 0);
        }
    }
    auto kth = [&](int v, long long k){
        for(int j=0; j<LOG && v; ++j){
            if(k & (1LL<<j)) v = up[j][v];
        }
        return v;
    };
    while(q--){
        int x; long long k;
        cin >> x >> k;
        int ans = kth(x, k);
        cout << (ans? ans : -1) << "\n";
    }
    return 0;
}

題目2:Company Queries II

原題:
https://cses.fi/problemset/task/1688

題意:
同一棵樹（以 1 為根），處理 q 次查詢：輸出節點 a 與 b 的 LCA。

解題思路:
建圖、以 1 為根 DFS 得 depth[] 與 up[v][j]。
實作 lca(u,v)：先拉平深度，再自高位往低位同步跳。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, q;
    cin >> n >> q;
    const int LOG = 20;
    vector<vector<int>> g(n+1);
    vector<vector<int>> up(LOG, vector<int>(n+1, 0));
    vector<int> depth(n+1, 0);

    for(int v=2; v<=n; ++v){
        int p; cin >> p;
        g[p].push_back(v);
        g[v].push_back(p);
    }

    // DFS 建 depth 與 up
    {
        int root = 1;
        vector<int> st = {root}, parent(n+1, 0);
        parent[root] = 0; depth[root] = 0;
        while(!st.empty()){
            int u = st.back(); st.pop_back();
            up[0][u] = parent[u];
            for(int v: g[u]){
                if(v == parent[u]) continue;
                parent[v] = u;
                depth[v] = depth[u] + 1;
                st.push_back(v);
            }
        }
        for(int j=1; j<LOG; ++j){
            for(int v=1; v<=n; ++v){
                int mid = up[j-1][v];
                up[j][v] = (mid ? up[j-1][mid] : 0);
            }
        }
    }

    auto lift = [&](int v, int k){
        for(int j=0; j<LOG && v; ++j)
            if(k & (1<<j)) v = up[j][v];
        return v;
    };
    auto lca = [&](int a, int b){
        if(depth[a] < depth[b]) swap(a,b);
        a = lift(a, depth[a]-depth[b]);
        if(a==b) return a;
        for(int j=LOG-1; j>=0; --j){
            if(up[j][a] != up[j][b]){
                a = up[j][a];
                b = up[j][b];
            }
        }
        return up[0][a]; // 其父即 LCA
    };

    while(q--){
        int a,b;
        cin >> a >> b;
        cout << lca(a,b) << "\n";
    }
    return 0;
}

四、Leetcode觀念說明

題目1:Lowest Common Ancestor of a Binary Tree

原題:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

題意:
給二元樹根 root 與節點 p,q，求兩者之 最近共同祖先。

解題思路:

• 標準遞迴：在子樹內若同時找到了 p 和 q，「第一次匯合」的節點就是 LCA。
• 寫法：dfs(u) 回傳是否在此子樹找到 p/q；若「左+右+當前」滿足兩者，更新答案。

/**
 * Definition for a binary tree node.
 * struct TreeNode { int val; TreeNode *left; TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
 * };
 */
class Solution {
    TreeNode* ans = nullptr;
    bool dfs(TreeNode* u, TreeNode* p, TreeNode* q){
        if(!u) return false;
        bool L = dfs(u->left, p, q);
        bool R = dfs(u->right, p, q);
        bool C = (u==p || u==q);
        if((L&&R) || (C&&(L||R))) ans = u;
        return L || R || C;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

題目2:Lowest Common Ancestor of a Binary Search Tree

原題:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

題意:
同 LCA，但樹是 BST。利用 BST 的序性加速。

解題思路

• 迭代或遞迴：
  • 若 p.val < root.val 且 q.val < root.val，往左；
  • 若都大於，往右；
  • 否則 root 即 LCA。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int a = p->val, b = q->val;
        while(root){
            if(a < root->val && b < root->val) root = root->left;
            else if(a > root->val && b > root->val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};